package q729_MyCalendar;

import java.util.TreeMap;

public class MyCalendar2 {
    TreeMap<Integer, Integer> calendar;

    MyCalendar2() {
        calendar = new TreeMap();
    }

    /*
    首先要弄清楚treeMap的结构是什么
    在我们没有对其进行任何设置的时候 TreeMap默认将会把我们传入的键值对按照 key 的大小进行从小到大排列
    在遍历的时候即可印证这一点
    了解了这一点之后 我们就可以利用这点特性 进行二分查找来解决该题
    treeMap中提供了几个关键方法可以使用
    floorKey用于返回小于/等于给定键元素(key_ele)的最大键元素(如果存在)，否则，当不存在该键元素时返回null
    而
    ceilingKey的作用是 返回大于/等于key的最小的键值对所对应的KEY，没有的话返回null

    所以很容易就可以利用这一点 我们查找当前传入的start两侧最近的已经录入的start
    考虑 前面的区间终点是否小于 传入的起点 并且 后面区间的起点 是否大于 传入的终点
    如果满足就可以直接存入当前区间 并且返回true
     */
    public boolean book(int start, int end) {
        Integer prev = calendar.floorKey(start),
                next = calendar.ceilingKey(start);
        if ((prev == null || calendar.get(prev) <= start) &&
                (next == null || end <= next)) {
            calendar.put(start, end);
            return true;
        }
        return false;
    }

}
